package DMSXL._2024.DP;

public class uniquePathsWithObstacles {
    public static void main(String[] args) {
        int[][] ob = {{0,1,0,0,0},{1,0,0,0,0},{0,0,0,0,0},{0,0,0,0,0}};
        System.out.println(new uniquePathsWithObstacles().uniquePathsWithObstacles(ob));
    }
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int len = obstacleGrid.length, width = obstacleGrid[0].length;
        if(obstacleGrid[0][0] == 1 || obstacleGrid[len - 1][width - 1] == 1){
            return 0;
        }
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < width; j++) {
                System.out.print(obstacleGrid[i][j] + "  ");
            }
            System.out.println();
        }
        int[][] dp = new int[len][width];
        //初始化dp数组
        int num = 1;
        for (int i = 0; i < len; i++) {
            if(obstacleGrid[i][0] == 1){
                num = 0;
            }
            dp[i][0] = num;
        }
        num = 1;
        for (int i = 0; i < width; i++) {
            if(obstacleGrid[0][i] == 1){
                num = 0;
            }
            dp[0][i] = num;
        }
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < width; j++) {
                System.out.print(dp[i][j] + "  ");
            }
            System.out.println();
        }
        //障碍物更新为0
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < width; j++) {
                //找到障碍物，dp数组更新为-1,代表不通
                if(obstacleGrid[i][j] == 1){
                    dp[i][j] = -1;
                }
            }
        }
        for (int i = 1; i < len; i++) {
            for (int j = 1; j < width; j++) {
                //如果是障碍物的位置直接跳过
                if(dp[i][j] == -1){
                    continue;
                }
                if(dp[i - 1][j] == -1 && dp[i][j - 1] == -1){
                    dp[i][j] = 0;
                }else if (dp[i - 1][j] == -1 || dp[i][j - 1] == -1) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + 1;
                }else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }

        return dp[len - 1][width - 1];
    }
}
